package leetcode.Top100;

import leetcode.Head;
import leetcode.ListNode;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 148. 排序链表
 */
public class Top053_LC148 {
    // 归并排序
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode middleNode = getMiddle(head);
        ListNode rightHead = middleNode.next;
        middleNode.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);
        return mergeSortList(left, right);
    }

    public ListNode getMiddle(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head, fast = head.next.next;
        while (fast!=null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public ListNode mergeSortList(ListNode leftHead, ListNode rightHead) {
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while (leftHead!=null && rightHead!=null) {
            if (leftHead.val < rightHead.val) {
                cur.next = leftHead;
                leftHead = leftHead.next;
            } else {
                cur.next = rightHead;
                rightHead = rightHead.next;
            }
            cur = cur.next;
        }
        cur.next = leftHead != null ? leftHead : rightHead;
        return head.next;
    }

    // 暴力排序
    public ListNode sortList2(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            list.add(cur.val);
            cur = cur.next;
        }
        list.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Integer.compare(o1, o2);
            }
        });
        ListNode newHead = new ListNode(-1);
        ListNode newCur = newHead;
        for (int i=0; i<list.size(); i++) {
            newCur.next = new ListNode(list.get(i));
            newCur = newCur.next;
        }
        return newHead.next;
    }

    public static void main(String[] args) {
        Top053_LC148 demo = new Top053_LC148();
        int[] arr = {-1,5,3,4,0};
        ListNode head = demo.sortList(Head.genList(arr));
        Head.printList(head);
    }
}
